import java.util.Stack;

public class Test {

    //是否有序
    private static boolean isSort(TreeNode root) {
        if(root == null) {
            return true;
        }

        int prevVal = Integer.MIN_VALUE;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null && ! stack.empty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            while(!stack.empty()) {
                TreeNode del = stack.pop();
                int val = del.val;

                if(prevVal >= val) {
                    return false;
                } else {
                    prevVal = val;
                }

                if(del.right != null) {
                    //找到非空结点出循环
                    cur = cur.right;
                    break;
                }
            }
        }

        return true;
    }

    //是否有序
    private static void isSort2(TreeNode root) {
        if(root == null) {
            return;
        }
        isSort2(root.left);
        System.out.print(root.val + " ");
        isSort2(root.right);
    }

    //是否平衡
    private static boolean isBalance(TreeNode root) {
        if(root == null) {
            return true;
        }

        int result = getHeight(root);

        return true;
    }

    private static int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int leftHeight = getHeight(root.left);
        if(leftHeight == -1) {
            return -1;
        }

        int rightHeight = getHeight(root.right);
        if(leftHeight == -1) {
            return -1;
        }

        if(rightHeight - leftHeight != root.bf) {
            System.out.println(root.bf + "平衡因子有误！！！");
            return -1;
        }

        if(Math.abs(rightHeight - leftHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight,rightHeight) + 1;
    }

    public static void main(String[] args) {
        //测试AVL 树
        AVLTree avlTree = new AVLTree();
        avlTree.insert(16);
        avlTree.insert(3);
        avlTree.insert(7);
        avlTree.insert(11);
        avlTree.insert(9);
        avlTree.insert(26);
        avlTree.insert(18);
        avlTree.insert(14);
        avlTree.insert(15);

        System.out.println(isBalance(avlTree.root));
        isBalance(avlTree.root);

    }

    public static void main1(String[] args) {
        //测试AVL 树
        AVLTree avlTree = new AVLTree();
        avlTree.insert(4);
        avlTree.insert(2);
        avlTree.insert(6);
        avlTree.insert(1);
        avlTree.insert(3);
        avlTree.insert(5);
        avlTree.insert(15);
        avlTree.insert(7);
        avlTree.insert(16);
        avlTree.insert(14);

        System.out.println(isSort(avlTree.root));
        isBalance(avlTree.root);
    }
}
